package DataStructrue.dp;

import java.util.Arrays;

//动态规划(背包问题,多属性限制下求最优解)
public class DP {
    static int lim=10;//单个属性限制
    static int[][] arr=new int[10][];//物品属性(cost,val,...)
    static int[][] mm=new int[arr.length][lim+1];//存储体


    public static void main(String[] args) {
        //初始化未存储状态
        for (int[] ints : mm) {
            Arrays.fill(ints, -1);
        }

        dfs01Bag(0,lim);

        //查询达到最低要求需要的最小限制
        for (int i = 0; i < lim + 1; i++) {
            if(mm[arr.length-1][i]>5){
                System.out.println(i);
            }
        }
    }

    //搜索DP,考虑"选择[idx,end]的物品"的方案
    static int dfs01Bag(int idx,int res){
        //边界条件
        if(idx==arr.length) return 0;
        //查询存储
        if(mm[idx][res]!=-1)
            return mm[idx][res];
        //不选的状态变化
        //计算不选择结果
        int nsl=dfs01Bag(idx+1,res);
        int sl=0;
        //满足条件则选择
        if(res-arr[idx][0]>=0){
            //选择的状态变化
            //计算选择结果
            sl=dfs01Bag(idx+1,res-arr[idx][0])+arr[idx][1];
        }
        //存储结果
        return mm[idx][res]=Math.max(nsl,sl);
    }
    //递推DP(优化空间)
    static int rcs01Bag(){
        int[] mm=new int[lim+1];//初始边界条件为0
        //考虑"选择[idx,end]的物品"的方案
        for (int idx = arr.length-1; idx >= 0; idx--) {
            //递推"限制为res"的结果
            for (int res = lim; res >= 0; res--) {
                //计算不选择结果
                int nsl=mm[res];
                int sl=0;
                //满足条件则选择(在未选择该物品的基础上)
                if(res-arr[idx][0]>=0){
                    //计算选择结果
                    sl=mm[res-arr[idx][0]]+arr[idx][1];
                }
                mm[res]=Math.max(nsl,sl);
            }
        }
        return mm[lim];
    }
    //完全背包
    static int allBag(){
        int[] mm=new int[lim+1];//初始边界条件为0
        //考虑"选择[idx,end]的物品"的方案
        for (int idx = arr.length-1; idx >= 0; idx--) {
            //递推"限制为res"的结果
            for (int res = 0; res <= lim; res++) {
                //计算不选择结果
                int nsl=mm[res];
                int sl=0;
                //满足条件则选择(在已选择该物品的基础上)
                if(res-arr[idx][0]>=0){
                    //计算选择结果
                    sl=mm[res-arr[idx][0]]+arr[idx][1];
                }
                mm[res]=Math.max(nsl,sl);
            }
        }
        return mm[lim];
    }
}
